import sortedcontainers


class Solution(object):
    def medianSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[float]
        """
        n = len(nums)
        if k == 1:
            return nums
        stack = sortedcontainers.SortedList(nums[:k])
        out = []

        def find():
            if k % 2 == 1:
                out.append(stack[k // 2])
            else:
                out.append((stack[k // 2 - 1] + stack[k // 2]) / 2)

        find()
        for i in range(n - k):
            stack.remove(nums[i])
            stack.add(nums[i + k])
            find()

        return out


data = Solution()
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(data.medianSlidingWindow(nums, k))
